// https://leetcode.cn/problems/kth-largest-element-in-an-array/

// 题干：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//       请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//       你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

// 示例：输入: [3,2,1,5,6,4], k = 2
//       输出: 5

// 碎语：同样是快速选择，时间复杂度为O(N)，亮点在于运用了递归
//       随机选数的细节也值得思考，先种下随机数种子，再用randi模上长度再加上左偏移
//       成功了制造了一个区间内随机的数key
//       快速选择排序后的数组分为三个区间，小于key，等于key，大于key

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        // 参数不够，再设一个函数
        // 先种下一个随机数种子
        srand(time(NULL));

        return qSelect(nums, 0, nums.size() - 1, k);
    }

    int qSelect(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];

        // 1.先随机选择一个key
        int key = getRandom(nums, l, r);

        // 2.快速选择排序
        int left = l - 1, right = r + 1, cur = l;
        while (cur < right){
            if (nums[cur] < key) swap(nums[cur++], nums[++left]);
            else if (nums[cur] == key) cur++;
            else swap(nums[cur], nums[--right]);
        }

        // 3.分类讨论
        // 现在[l, left]为小于key，[left+1,right-1]为等于key，[right,r]为大于key
        int c = r - right + 1, b = right - left - 1; // b,c表示区间长度

        if (c >= k) return qSelect(nums, right, r, k); // 此时所求数必在[right,r]区间内
        else if (b + c >= k) return key; // 所求数就是key！
        else return qSelect(nums, l, left, k - b - c); // 此时所求数必在[l, left]区间内，但此时递归注意求的是第k-b-c个数
    }

    int getRandom(vector<int>& nums, int l, int r)
    {
        int randi = rand() % (r - l + 1) + l;

        return nums[randi];
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {3,2,1,5,6,4};

    cout << sol.findKthLargest(nums, 3) << endl;

    return 0;
}